In previous work, the author introduced the B-treap, a uniquely representedB-tree analogue, and proved strong performance guarantees for it. However, theB-treap maintains complex invariants and is very complex to implement. In thispaper we introduce the B-skip-list, which has most of the guarantees of theB-treap, but is vastly simpler and easier to implement. Like the B-treap, theB-skip-list may be used to construct strongly history-independent indexstructures and filesystems; such constructions reveal no information about thehistorical sequence of operations that led to the current logical state. Forexample, a uniquely represented filesystem would support the deletion of a filein a way that, in a strong information-theoretic sense, provably removes allevidence that the file ever existed. Like the B-tree, the B-skip-list has depthO(log_B (n)) where B is the block transfer size of the external memory, useslinear space with high probability, and supports efficient one-dimensionalrange queries.
展开▼
